package seqlist.oj;

/**
 * 反转单链表
 */
public class Num206 {
    // 1.头插法
//    public ListNode reverseList(ListNode head) {
//        // 先判断边界条件
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode newHead = null;
//        while (head != null) {
//            // 遍历原链表，取出值，新建节点，头插入新的链表中
//            ListNode node = new ListNode(head.val);
//            node.next = newHead;
//            newHead = node;
//            head = head.next;
//        }
//        return newHead;
//    }
//    // 2.原地移动原链表
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode prev = null;
//        ListNode cur = head;
//        while (cur != null) {
//            // 使用next暂存下一个要处理的节点
//            ListNode next = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        return prev;
//    }

    // 3.递归法
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 此时第二个节点以及之后节点的反转工作交给reverseList()执行，并且，返回的链表头就是最终的返回值
        ListNode secNode = head.next;
        ListNode newHead = reverseList(head.next);
        secNode.next = head;
        head.next = null;
        return newHead;
    }
}
